package Easy;

// 122.买卖股票的最佳时机II
// 思路：贪心，只要涨了我就卖，然后跌了我就买。买的前提是确保他会涨,卖的前提是确保他会跌
// 例：[6,1,3,2,4,7]
// 如果用上面的算法，找到7比6大，所以最后结果是1，但是最好的结果应该是（3-1）+（7-2）=7
// 所以外面还要再套一层，表示从第一个点开始找的情况，第二个点开始找的情况...最后选出max
// 这样还是不行，因为例：[2,1,2,1,0,1,2]，第四个数是1，找到比它大的2，循环结束。

// 换思路：
// dp[i-1] = dp[i] + prices[i-1]<prices[i] ? prices[i]-prices[i-1] : 0;
// dp[i]表示 到i点为止，最大的收益。 从后往前算
public class Solution122 {
    public static int maxProfit(int[] prices) {
        int dp[] = new int[prices.length];
        for (int i = prices.length - 2; i >= 0; i--) {
            dp[i] =  prices[i] < prices[i + 1] ? prices[i + 1] - prices[i] + dp[i+1] : dp[i+1];
        }
        return dp[0];
    }

    public static void main(String[] args) {
        maxProfit(new int[]{7, 1, 5, 3, 6, 4});
    }
}
